package main.剑指OfferⅡ;

import java.util.*;

public class Day13_Day16 {
    public static void main(String[] args) {
        System.out.println("**************************Day13**************************");
        System.out.println("剑指OfferⅡ039.直方图最大矩形面积");
        System.out.println("剑指OfferⅡ040.矩阵中最大的矩形");
        System.out.println("**************************Day14**************************");
        System.out.println("剑指OfferⅡ041.滑动窗口的平均值");
        System.out.println("剑指OfferⅡ042.最近请求次数");
        System.out.println("剑指OfferⅡ043.往完全二叉树添加节点");
        System.out.println("**************************Day15**************************");
        System.out.println("剑指OfferⅡ044.二叉树每层的最大值");
        System.out.println("剑指OfferⅡ045.二叉树最底层最左边的值");
        System.out.println("剑指OfferⅡ046.二叉树的右侧视图");
        System.out.println("**************************Day16**************************");
        System.out.println("剑指OfferⅡ047.二叉树剪枝");
        System.out.println("剑指OfferⅡ048. 序列化与反序列化二叉树");
        System.out.println("剑指OfferⅡ049. 从根节点到叶节点的路径数字之和");
    }
}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
      this.val = val;
      this.left = left;
      this.right = right;
    }
}

class Offer39{
    public int largestRectangleArea(int[] heights) {
        int n = heights.length;
        int[] left = new int[n];
        int[] right = new int[n];

        Deque<Integer> mono_stack = new ArrayDeque<Integer>();
        for (int i = 0; i < n; ++i) {
            while (!mono_stack.isEmpty() && heights[mono_stack.peek()] >= heights[i]) {
                mono_stack.pop();
            }
            left[i] = (mono_stack.isEmpty() ? -1 : mono_stack.peek());
            mono_stack.push(i);
        }

        mono_stack.clear();
        for (int i = n - 1; i >= 0; --i) {
            while (!mono_stack.isEmpty() && heights[mono_stack.peek()] >= heights[i]) {
                mono_stack.pop();
            }
            right[i] = (mono_stack.isEmpty() ? n : mono_stack.peek());
            mono_stack.push(i);
        }

        int ans = 0;
        for (int i = 0; i < n; ++i) {
            ans = Math.max(ans, (right[i] - left[i] - 1) * heights[i]);
        }
        return ans;
    }
}

class Offer40{
    public int maximalRectangle(String[] matrix) {
        int m = matrix.length;
        if (m == 0)  return 0;
        int n = matrix[0].length();
        int[][] left = new int[m][n];

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i].charAt(j) == '1') {
                    left[i][j] = (j == 0 ? 0 : left[i][j - 1]) + 1;
                }
            }
        }

        int ret = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i].charAt(j) == '0') continue;
                int width = left[i][j];
                int area = width;
                for (int k = i - 1; k >= 0; k--) {
                    width = Math.min(width, left[k][j]);
                    area = Math.max(area, (i - k + 1) * width);
                }
                ret = Math.max(ret, area);
            }
        }
        return ret;
    }
}

class Offer41{
    List<Integer> numList;
    int sum,size;
    /** Initialize your data structure here. */
    public Offer41(int size) {
        numList=new ArrayList<>();
        sum=0;
        this.size=size;
    }

    public double next(int val) {
        double average=0;
        if (numList.size()<size){
            sum+=val;
            numList.add(val);
            average=(sum*1.0)/numList.size();
        }else {
            int first=numList.get(0);
            sum-=first;
            sum+=val;
            numList.remove(0);
            numList.add(val);
            average=(sum*1.0)/size;
        }
        return average;
    }
}

class Offer42{
    List<Integer> list;
    public Offer42() {
        list=new ArrayList<>();
    }

    public int ping(int t) {
        list.add(t);
        int lowIndex=0,lowVal=t-3000,left=0,right=list.size()-1;
        while (left<right){
            int midIndex=left+(right-left)/2,midVal=list.get(midIndex);
            if (midVal<lowVal){
                left=midIndex+1;
            }else {
                right=midIndex;
            }
        }

        return list.size()-left;
    }
}

class Offer43{
    TreeNode root;
    Queue<TreeNode> qu = new LinkedList<>();
    public Offer43(TreeNode root) {
        this.root = root;

        qu.offer(root);
        while(qu.peek().left != null && qu.peek().right != null){
            TreeNode node = qu.poll();
            qu.offer(node.left);
            qu.offer(node.right);
        }
    }

    public int insert(int v) {

        TreeNode father = qu.peek();
        if(father.left == null){
            father.left = new TreeNode(v);
        }else{
            father.right = new TreeNode(v);
            qu.poll();
            qu.offer(father.left);
            qu.offer(father.right);
        }

        return father.val;
    }

    public TreeNode get_root() {
        return this.root;
    }
}

class Offer44{
    public List<Integer> largestValues(TreeNode root) {
        List<Integer> list=new ArrayList<>();
        if (root!=null){
            int curCount=1,nextCount=0,max=Integer.MIN_VALUE;
            Deque<TreeNode> deque=new LinkedList<>();
            deque.addFirst(root);
            while (!deque.isEmpty()){
                TreeNode curNode=null;
                if (curCount>0){
                    curNode=deque.pollFirst();
                    curCount--;
                }else {
                    list.add(max);//上层最大值
                    max=Integer.MIN_VALUE;//重置
                    curCount=nextCount;
                    nextCount=0;
                    curCount--;
                    curNode=deque.pollFirst();

                }
                max=Math.max(max, curNode.val);
                if (curNode.left!=null){
                    nextCount++;
                    deque.addLast(curNode.left);
                }
                if (curNode.right!=null){
                    nextCount++;
                    deque.addLast(curNode.right);
                }
            }
            list.add(max);
        }
        return list;
    }
}

class Offer45{
    public int findBottomLeftValue(TreeNode root) {
        int lowestLeft= root.val, curLevel=1,nextLevel=0;
        Deque<TreeNode> deque=new LinkedList<>();
        deque.add(root);
        TreeNode curNode=null;
        while (!deque.isEmpty()){
            if (curLevel>0){
                curNode=deque.pollFirst();
                curLevel--;
            }else {
                curLevel=nextLevel;
                nextLevel=0;
                curLevel--;
                curNode=deque.pollFirst();
                lowestLeft= curNode.val;
            }
            if (curNode.left!=null){
                nextLevel++;
                deque.addLast(curNode.left);
            }
            if (curNode.right!=null){
                nextLevel++;
                deque.addLast(curNode.right);
            }
        }
        return lowestLeft;
    }
}

class Offer46{
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> list=new ArrayList<>();
        if (root!=null){
            TreeNode curNode=null;
            Deque<TreeNode> deque=new LinkedList<>();
            int curLevel=1,nextLevel=0;
            deque.addLast(root);
            while (!deque.isEmpty()){
                if (curLevel>0){
                    if (curLevel==1){
                        curNode=deque.pollFirst();
                        curLevel--;
                        list.add(curNode.val);
                    }else {
                        curNode=deque.pollFirst();
                        curLevel--;
                    }
                }else {
                    if (nextLevel!=1){
                        curLevel=nextLevel;
                        nextLevel=0;
                        curLevel--;
                        curNode=deque.pollFirst();
                    }else {
                        curLevel=nextLevel;
                        nextLevel=0;
                        curLevel--;
                        curNode=deque.pollFirst();
                        list.add(curNode.val);
                    }
                }
                if (curNode.left!=null){
                    nextLevel++;
                    deque.addLast(curNode.left);
                }
                if (curNode.right!=null){
                    nextLevel++;
                    deque.addLast(curNode.right);
                }
            }
        }
        return list;
    }
}

class Offer47{
    public boolean process(TreeNode root){
        if (root==null) return true;//空节点
        boolean left=process(root.left),right=process(root.right);//左右子树情况
        if (left&&right&&root.val==0) {//左右子树为空，本节点为0
            return true;
        }else {
            if (left) root.left=null;
            if (right) root.right=null;
            return false;
        }

    }
    public TreeNode pruneTree(TreeNode root) {
        boolean left=process(root.left),right=process(root.right);
        if (left) root.left=null;
        if (right) root.right=null;
        if (left&&right&&root.val==0) root=null;
        return root;
    }
}

class Offer48{
    public String serialize(TreeNode root) {
        return rserialize(root, "");
    }

    public TreeNode deserialize(String data) {
        String[] dataArray = data.split(",");
        List<String> dataList = new LinkedList<String>(Arrays.asList(dataArray));
        return rdeserialize(dataList);
    }

    public String rserialize(TreeNode root, String str) {
        if (root == null) {
            str += "null,";
        } else {
            str += str.valueOf(root.val) + ",";
            str = rserialize(root.left, str);
            str = rserialize(root.right, str);
        }
        return str;
    }

    public TreeNode rdeserialize(List<String> dataList) {
        if (dataList.get(0).equals("null")) {
            dataList.remove(0);
            return null;
        }

        TreeNode root = new TreeNode(Integer.valueOf(dataList.get(0)));
        dataList.remove(0);
        root.left = rdeserialize(dataList);
        root.right = rdeserialize(dataList);
        return root;
    }
}

class Offer49{
    List<Integer> list;
    public void process(TreeNode curNode,String lastStr){
        StringBuffer curStr=new StringBuffer(lastStr);
        curStr.append(curNode.val);
        if (curNode.left==null&&curNode.right==null){
            list.add(Integer.valueOf(curStr.toString()));
            return;
        }
        if (curNode.left!=null) process(curNode.left,curStr.toString());
        if (curNode.right!=null) process(curNode.right,curStr.toString());
    }
    public int sumNumbers(TreeNode root) {
        int sum=0;
        list=new ArrayList<>();
        process(root,"");
        for (Integer num:list) sum+=num;
        return sum;
    }
}